#!/usr/bin/perl
#!/usr/local/bin/perl
#############################
# group.pl: created by Lihy #
#############################
# Implementation of Node Class, a node represents a tree. It has three methods: add,get,changeroot.
# Each node contains a hash with key '_parent', '_rightsibling', '_leftchild' whose values
# point to the corresponding things, and the '_root' key indicate the node's root.
# Of course, the '_key' means the content of the node.
# Some ambiguous or even loopback situation may arise when we invoke the 'add' method, like
# adding a child who haved a parent to another or adding the node's root as a child to itself.
# I avoid the first case by checking whether the child's _parent is defined, the add fails if true.
# I avoid the second case by using the _root key, if they both have the same _root, the add fails.
# But if not, I must fist change the child's descendants' _root to the new one (the method changeroot).

use strict;
use warnings;

################# Begin package Node ######################
package Node;
sub new
{
  my ($type,$key) = @_;               # The type name
  my $self = {};
  $self = {
    _parent => undef,
    _rightsibling => undef, 
    _leftchild_ => undef,
    _root => $self,
    _key => $key,
  };
  return bless $self, $type;   
}

sub add
{
  my ($self, $child) = @_;
  if (!defined($child) or defined($child->{_parent})) {  # Case 1
    warn "$0: Child Is Undef or Not RootNode!,$!";
    return;
  }
  if ($self->{_root} == $child->{_root}) {               # Case 2
    warn "$0: Can't Add Root As Child!,$!";
    return;
  }
  $child->{_parent} = $self; 
  $child->{_rightsibling} = undef;
  $child->changeroot($self->{_root});
  my $rightchild = $self->{_leftchild};
  if (defined($rightchild)) {
    while (defined($rightchild->{_rightsibling})) {
      $rightchild = $rightchild->{_rightsibling};
    }
    $rightchild->{_rightsibling} = $child;
  } else {
    $self->{_leftchild} = $child;
  }
}

sub get
{
  my $self = shift;
  my @member;
  my $child = $self->{_leftchild};
  if (defined($child)) {
    while (defined($child)) {
      my @mymember = &get($child);
      push (@member,@mymember);
      $child = $child->{_rightsibling};
    }
  } else {
    push (@member, $self);
  }
  return @member;
}

sub changeroot
{
  my ($self,$newroot) = @_;
  $self->{_root} = $newroot;
  my $child = $self->{_leftchild};
  if (defined($child)) {
    while (defined($child)) {
      $child->changeroot($newroot);
      $child = $child->{_rightsibling};
    }
  }
}
################# End package Node ######################

# The rest is just for test
my $rootnode = Node->new(0);
my $childnode1 = Node->new(1);
my $childnode2 = Node->new(2);

$childnode1->add($childnode2);
$rootnode->add($childnode2);  # no effect
$rootnode->add($childnode1);
$childnode2->add($rootnode);  # no effect
$rootnode->add(Node->new(4));
$rootnode->add(Node->new(8));

my @member = $rootnode->get();
print "member has $#member elements\n";
foreach my $member (@member) {
  print "$member->{_key}\n";
}

